RSA Cheat Sheet

Setup

$p =$ random prime number

$q =$ random prime number

$n = p*q$

$Φ(n) = (p - 1)(q - 1)$ (this is called the totient function)

$e =$ some number smaller than $Φ(n)$ that's coprime with it (shares no factors)

Calculate d with:

$de = 1 \mod Φ(n)$

Public key: $n, e$

Private key: $p, q, d$

$m =$ message, $c =$ ciphertext

Encryption

$c = m^e \mod n$

Decryption

$m = c^d \mod n$

Signing

$s$ is signature

$s = m^d \mod n$

Verification

Verify by checking if $s^e = m$